package tcts0421;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
// https://leetcode-cn.com/problems/merge-intervals/
public class lc56合并区间0424 {

        public int[][] merge(int[][] intervals) {
            // 1. 按照区间左边的值进行升序排列
            Arrays.sort(intervals, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            // 2. 初始化 outputs, 用于存储合并之后区间结果的动态数组
            ArrayList<int[]> outputs = new ArrayList<>();
            // 3. 遍历处理每一个区间
            for (int i = 0; i < intervals.length; i++) {
                int[] currInterval = intervals[i];
                if (outputs.isEmpty()) {
                    outputs.add(currInterval);
                } else { // 判断是否有重叠，有的话则合并
                    int[] outputsLastInterval = outputs.get(outputs.size() - 1);
                    int outputLastRight = outputsLastInterval[1];
                    int currLeft = currInterval[0];
                    if (outputLastRight < currLeft) { // 没有重叠
                        outputs.add(currInterval);
                    } else { // 重叠，合并
                        int currRight = currInterval[1];
                        outputsLastInterval[1] = Math.max(outputLastRight, currRight);
                    }
                }
            }
            return outputs.toArray(new int[outputs.size()][]);
        }

    public static void main(String[] args) {
        int arr[][] = new lc56合并区间0424().merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(" "+arr[i][j]);
            }
            System.out.println();
        }
    }

}
